1. Field of the Invention
The present invention generally relates to computer processing techniques and, in particular, to a superscalar processing system and method that detect data hazards within instruction groups of a computer program.
2. Related Art
Parallel processing, sometimes known as superscalar processing, has been developed to reduce the amount of time required to process instructions of a computer program. In parallel processing, at least two pipelines are defined that simultaneously execute instructions. One type of parallel processing is out-of-order processing, in which each pipeline of a processor simultaneously executes different instructions independently of the other pipeline(s).
In out-of-order processing, the instructions are not necessarily input into the pipelines in the same order that they were received by the processor. In addition, it typically takes different amounts of time for different instructions to execute, and it is, therefore, possible for an instruction to be fully executed before another instruction, even though the other instruction was input into its respective pipeline first. Accordingly, instructions are not necessarily executed in the same order that they are received by the pipelines within the processor, and as a result, the complexity of preventing errors from read-after-write data hazards and write-after-write data hazards, which will be described in more detail below, is relatively large for out-of-order processing.
A xe2x80x9cread-after-write data dependencyxe2x80x9d exists when one instruction to be executed by a processor utilizes, during execution, data retrieved or produced from the execution of another instruction. If the one instruction executes before the other instruction executes, then an error may occur, since the one instruction may utilize incorrect data during execution. As a result, to prevent errors, steps should be taken to ensure that the instruction utilizing data retrieved or produced from the execution of another instruction does not execute until the necessary data from execution of the other instruction is available. If a read-after-write data dependency exists and if such steps are not taken, then a xe2x80x9cread-after-write data hazardxe2x80x9d exists, since the read-after-write data dependency may result in the utilization of incorrect data.
A xe2x80x9cwrite-after-write data hazardxe2x80x9d exists when an older instruction, during execution, may write data to the same register or other memory location written to by a younger instruction and incorrectly overwrite valid data written by the younger instruction. An instruction is xe2x80x9cyoungerxe2x80x9d than another instruction when it is received by a processor after the other instruction. Conversely, an instruction is xe2x80x9colderxe2x80x9d than another instruction when it is received by a processor before the other instruction.
As an example of a write-after-write data hazard, assume that a first instruction is a load instruction that retrieves data and writes the retrieved data to a particular register. It may take a relatively long time for the data to be retrieved, particularly if the data to be retrieved is not locally available. Therefore, it is possible for a second instruction (i.e., an instruction younger than the first instruction) to write data to the same register after the first instruction has executed but before the data retrieved by the first instruction is written to the register. In such a case, the data written to the register by the second instruction may be overwritten by the data retrieved by the first instruction. As a result, the register may contain incorrect data, and an error may result when a later instruction uses the data in the register.
To prevent errors from read-after-write data hazards and from write-after-write data hazards, most out-of-order parallel processors employ a control mechanism. In this regard, during the execution of each instruction, the control mechanism determines whether an instruction being processed (referred to hereafter as the xe2x80x9cpending instructionxe2x80x9d) requires data produced by the execution of an older instruction. If so, the control mechanism then determines whether the older instruction has been processed, at least to the point where the needed data is available. If this data is not yet available, the control mechanism stalls (i.e., temporarily stops) processing of the pending instruction until the necessary data becomes available, thereby preventing errors from read-after-write data hazards.
In addition, the control mechanism also determines whether data from (i.e., generated or retrieved by) an older instruction is to be written to the same register or memory location as the data from a pending instruction. If so, the control mechanism stalls the pending instruction until the data from the older instruction has been written to the register or memory address, thereby preventing errors from write-after-write data hazards. Consequently, the control mechanism may stall the pending instruction in order to prevent errors from either read-after-write data hazards or from write-after-write data hazards.
Stalling of the pending instruction is usually accomplished by asserting a stall signal transmitted to the pipeline executing the pending instruction. In response to the asserted stall signal, the pipeline is designed to stop execution of the pending instruction until the stall signal is deasserted by the control mechanism. Once the read-after-write data hazard or the write-after-write data hazard no longer exists, the control mechanism deasserts the stall signal, and in response, the pipeline resumes processing of the pending instruction. The control mechanism required to detect and prevent potential errors from read-after-write data hazards and from write-after-write data hazards is relatively complex in out-of-order processors, and as the number of pipelines is increased, the complexity of the control mechanism increases dramatically.
As a result, many conventional parallel processors, particularly processors having a large number of pipelines, employ an in-order type of processing in lieu of the out-of-order type of processing described above. In in-order processing, the instructions being processed by the different pipelines are stepped through the stages of the pipelines on certain edges of a system clock signal. In this regard, the processing of instructions in a pipeline is usually divided into stages, and each stage of the pipeline simultaneously processes a different instruction.
As an example, the processing performed by each pipeline may be divided into a register stage, an execution stage, a detect exceptions stage, and a write stage. During the register stage, any operands necessary for the execution of an instruction are obtained. Once the operands have been obtained, the processing of the instruction enters into the execution stage in which the instruction is executed. After the instruction has been executed, the processing of the instruction enters into a detect exceptions stage in which conditions, such as overruns during execution, for example, that may indicate data unreliability are checked. After the detect exceptions stage is completed, a write stage is entered in which the results of the execution stage are written to a register.
A key feature of in-order processing is that each instruction of an issue group steps through each stage at the same time. An xe2x80x9cissue group,xe2x80x9d as defined herein, is a set of instructions simultaneously (i.e., during the same clock cycle) processed by the same stage of different pipelines within a single processor. As an example, assume that each stage of each pipeline processes one instruction at a time, as is typically done in the art. The instructions in the detect exceptions stage of the pipelines form a first issue group, and the instructions in the execution stage of the pipelines form a second issue group. Furthermore, the instructions in the register stage of the pipelines form a third issue group. In the absence of a stall, each of the issue groups advances into the next respective stage in response to an active edge of the system clock signal. In other words, the first issue group steps into the write stage, the second issue group steps into the detect exceptions stage, and the third issue group steps into the execution stage in response to an active edge of the system clock signal.
As used herein, an xe2x80x9cactive edgexe2x80x9d is any edge of the system clock signal, the occurrence of which induces each unstalled instruction in a pipeline to advance to the next stage of processing in the pipeline. For example, assume that a processor is designed to step each unstalled instruction into the next stage of processing every three clock cycles. In this example, the active edges could be defined as every third rising edge of the clock signal. It should be noted that which edges of the clock signal are designated as xe2x80x9cactive edgesxe2x80x9d is based on design parameters and may vary from processor to processor.
During in-order processing, any instruction in one issue group preferably does not pass another instruction in another issue group. In other words, instructions of one issue group input into the pipelines after the instructions of another issue group are prevented from entering into the same stage processing any of the instructions of the other issue group. Therefore, at any point in time, each stage of the pipelines is respectively processing instructions from only one issue group. Since instructions from different issue groups are prevented from passing each other, the control mechanism for controlling the pipelines and for stalling instructions to prevent errors from read-after-write data hazards and from write-after-write data hazards is greatly simplified and is, therefore, often preferable over out-of-order processing.
However, errors from read-after-write data hazards and write-after-write data hazards are not adequately prevented in some in-order processors. In this regard, an instruction dispersal unit (IDU) is often utilized to define the issue groups that are processed by the processor pipelines. Furthermore, in some in-order processors, such as processors that utilize explicitly parallel instruction computing (EPIC), for example, the instructions are transmitted to the IDU in instruction groups. An instruction group is a set of instructions guaranteed by a compiler or some other device external to the processor not to have read-after-write data hazards or write-after-write data hazards between the instructions of the set.
For example, many compilers sequentially transmit instructions to the IDU. In compiling the instructions, the compiler may determine whether read-after-write data hazards or write-after-write data hazards exist. To optimize performance, the compiler may define an instruction group by inserting stop bits so that the IDU can more efficiently process the instructions. As used herein, a xe2x80x9cstop bitxe2x80x9d is a bit inserted between instructions being transmitted to a processing system, wherein the bit can be appropriately asserted or deasserted to indicate the start or end of an instruction group.
For example, the compiler can be designed to determine when consecutively transmitted instructions define an instruction group and to assert a stop bit before the first instruction in the group and after the last instruction in the group. As a result, the instructions between asserted stop bits define an instruction group, and the IDU, therefore, should be aware that no instruction between asserted stop bits should have a read-after-write data hazard or a write-after-write data hazard with another instruction between the asserted stop bits. Therefore, in defining the issue groups, the IDU does not have to check for read-after-write data hazards and write-after write-hazards between the instructions in the instruction group.
However, a problem arises when the compiler incorrectly includes two instructions having a read-after-write data hazard or a write-after-write data hazard therebetween in the instruction group. Since the IDU may not be designed to check for read-after-write data hazards and write-after-write data hazards between instructions in the same instruction group (relying instead on the assertion/deassertion of stop bits to indicate read-after-write and write-after-write data hazards), the IDU may improperly define the issue groups such that two instructions in the same issue group have a read-after-write data hazard or a write-after-write data hazard therebetween. Having a read-after-write or write-after-write data hazard between two instructions of the same issue group violates the architecture of the in-order processor and may result in errors during processing of the two instructions by the processor pipelines.
Thus, a heretofore unaddressed need exists in the industry for providing a system and method of determining when an instruction group includes two instructions that have a read-after-write data hazard or a write-after-write data hazard therebetween.
The present invention overcomes the inadequacies and deficiencies of the prior art as discussed hereinbefore. Generally, the present invention provides a system and method for determining whether an instruction group includes an instruction defining a data hazard with another instruction of the same instruction group.
In architecture, the system of the present invention utilizes a memory, a plurality of pipelines, an instruction dispersal unit (IDU), and a control mechanism. The IDU receives an instruction group that includes a plurality of instructions and transmits the instructions of the instruction group to the plurality of pipelines. The control mechanism stores register identifiers of the instructions in the memory and determines whether a register identifier associated with one of the instructions is stored in the memory. When the register identifier associated with the one instruction is stored in the memory, the control mechanism transmits a warning signal. In response to the warning signal, a warning message may be produced to notify a user that two instructions of an instruction group define a read-after-write or a write-after-write data hazard, and/or further processing of the instructions may be terminated.
In accordance with other features of the present invention, the memory is content-addressable, and the control mechanism invalidates the data in memory when the control mechanism determines that each instruction of the instruction group has been analyzed by the control mechanism.
The present invention can also be viewed as providing a superscalar processing method for processing instructions of computer programs and for detecting hazards within the computer programs. The method can be broadly conceptualized by the following steps: defining an instruction group, the instruction group including a plurality of instructions; storing register identifiers associated with the instructions into memory; determining whether one of the register identifiers associated with one of the instructions is stored in the memory; and transmitting a warning signal in response to a determination in the determining step that the one register identifier associated with the one instruction is stored in the memory.
Other features and advantages of the present invention will become apparent to one skilled in the art upon examination of the following detailed description, when read in conjunction with the accompanying drawings. It is intended that all such features and advantages be included herein within the scope of the present invention and protected by the claims.